package written_examination_questions;

import java.util.Stack;

public class Demo20251119 {
    // 递归乘法
    public int multiply(int A, int B) {
        // 确保 A 是较小的数，减少递归深度
        if (A > B) return multiply(B, A);

        if (A == 0 || B == 0) return 0;
        if (A == 1) return B;

        // 如果B 是偶数，递归计算A ＊(B/2)，然后左移一位(相当于 ×2)
        if (B % 2 == 0) // B 是偶数
            return multiply(A, B >> 1) << 1; // B 的一半个 A 再乘 2
        else
            return A + multiply(A, B - 1);
    }
}

/**
 * 用栈实现队列
 */
class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}
